Kenneth H. Rosen编写的Discrete Mathematics and Its Applications 8th
原子命题:不能用更简单的命题来表达的命题。
| 符号 | 英文 | 中文 |
|---|---|---|
| negation | 反面,对立面(非) | |
| conjunction | 合取(与) | |
| disjunction | 析取(或) | |
| exclusive or | 异或(一真一假命题为真) |
| p | q | |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
逆命题(converse):
逆否命题(contrapositive):
双条件命题(biconditional statement):
一些标记:
| p | q | p only if q | q only if p | |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | T | T |
已知
逆命题(converse):
逆否命题(contrapositive):
否命题(inverse):
双条件命题(biconditional):
考虑一个复合命题:
| p | q | |||
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | T | F | F |
| F | T | F | F | T |
| F | F | T | F | F |
| Operator | Precedence |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
语句:“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”
逻辑:
语句:“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”
逻辑:
在布尔搜索中,连接的AND用于匹配同时包含两个搜索词的记录,连接的OR用于匹配两个搜索词中的一个或两个,连接的NOT(有时写成AND NOT)用于排除特定的搜索词。当使用布尔搜索来定位可能感兴趣的信息时,通常需要仔细规划如何使用逻辑连接词。
无论其中出现的命题变量的真值是多少,一个复合命题总是为真,这就叫做重言式(永真式,tautology)。一个总是假的复合命题叫做矛盾式(contradiction)。既不是永真式也不是矛盾式的复合命题称为可能式(contingency)。
如果
De Morgan法则:
条件析取等价:
分配律:
结合律:
吸收律:

证明
对于一个复合命题,如果给它的变量赋真值,使它为真(也就是说,当它是重言式或偶然性时),则称这个复合命题是可满足的。
应用:n-皇后问题
n皇后问题要求在一个n × n的棋盘上放置n个皇后,这样任何皇后都不能攻击另一个皇后。这意味着不能将两个皇后放在同一行、同列或同一对角线上。图1显示了8皇后问题的解决方案。(八皇后问题可以追溯到1848年,当时由马克斯·贝泽尔提出,并于1850年由弗朗茨·纳克彻底解决。
为了将建模n-皇后问题成一个满足性问题,我们引入
如果要求n个皇后没有两个在同一行,所以每行只有一个皇后,我们可以通过验证每行至少包含一个皇后,每行最多包含一个皇后来证明每行中有一个皇后。可以使用
对于每一行,让
对于每行最多只有一个皇后,对于整数j和k,且
同样对于每一列,有
要求对角线没有多个皇后,先看向左上的对角线
再看右下的对角线
最后需要满足可满足性为
还有数独的例子不过多赘述。
如让P(x)表示表述“x>3”,P(4)为真,P(3)为假。
前置条件和后置条件:谓词还可以用来验证计算机程序,也就是证明当给定合法输入时计算机程序总是能产生所期望的输出。(注意除非建立了程序的正确性,否则无论测试了多少次都不能证明程序对所有输入都产生所期望的输出,除非能测试到每个输入值。)描述合法输入的语句叫作前置条件,而程序运行的输出应该满足的条件称为后置条件。
考虑下面的程序
temp = x;x = y;y = temp;前置语句P(x,y):假设“x=a,y=b”成立,后置语句Q(x,y):“x=b, y=a”。
全称量词:许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真,这一特定域称为变量的论域(domain of discourse)(或全体域( universe of discourse)), 时常简称为域(domai n) 。这类语句可以用全称量化表示。
存在量词:许多数学定理断言:有一个个体使得某种性质成立。这类语句可以用存在量化表示。我们可以用存在批化构成这样一个命题:该命题为真当且仅当论域中至少有一个x的值使得P(x)为真。
| 命题 | 什么时候为真 | 什么时候为假 |
|---|---|---|
| 对每一个x,P(x)为真 | 有一个 x, 使 P(x)为假 | |
| 有一个x,使P(x)为真 | 对每一个x,P(x)都为假 |
当一个量词的域是有限的,则可以用命题逻辑来表示,当论域中的元素为
量词
用谓词和量词表达系统规范说明“每封大于1MB的邮件会被压缩”和“如果一个用户处于活动状态,那么至少有一条网络链路是有效的”。
“每封大于1MB的邮件会被压缩”:令S(m,y)表示邮件m大于yMB,其中变量的m的论域是所有邮件,变量y是一个正实数;令C(m)表示“邮件m会被压缩”。可以表述为:
“如果一个用户处于活动状态,那么至少有一条网络链路是有效的”:令A(u)表示“用户u处于活动状态”,其中变量u的论域是所有用户;令S(n,x)表示网络链路n处于x状态,其中n的论域是所有网络链路,x的论域是网络链路所有可能的状态。可以表述为:
一个量词出现在另一个量词的作用域,如
如
如
将“每个人恰好有一个最好的朋友”翻译成逻辑表达式
对于一个人x恰好有一个最好的朋友,可以表示为存在一个人y是x最好的朋友,同时其他不是y的人z都不是x最好的朋友,x最好的朋友是y用
直接连续地应用单个量词语句的否定规则即可
如
语句

命题
命题
全称实例(universal instantiation)是从给定前提
全称引入(universal generalization)是从对论域里所有元素c都有P(c)为真的前提推出
存在实例(existential instantiation)是允许从“如果我们知道
存在引入(existential generalization)是用来从“已知有一特定的c使P(c)为真时得出
全称假言推理(universal modus ponens):如果
证明方法
直接证明法:
反证法:
归谬证明法:
假设我们要证明命题p是真的。再假定我们能找到一个矛盾式q使得
如证明任意22天中至少有4天属于每星期的同一天
令p为命题“任意 22 天中至少有 4 天属于每星期的同一天”。假设
给出了许多证明方法和策略
穷举证明法和分情形证明法
存在性证明,构造性和非构造性
唯一性证明,要证存在性和唯一性
证明策略:正向推理和反向推理
寻找反例
证明策略实践:棋盘拼接问题
证明或驳斥:如果你有一个盛有8加仑水的瓶和两个容量分别为5加仑和3加仑的空瓶,那么你可以通过不断地把一瓶水全部或部分倒人另一个瓶中而测量出4加仑的水。
证明:令盛有8加仑水的瓶为A,容量为5加仑水的瓶为B,容量为3加仑的瓶为C
xxxxxxxxxx 8 0 0A -> C 5 0 3C -> B 5 3 0A -> C 2 3 3C -> B 2 5 1B -> A 7 0 1C -> B 7 1 0A -> C 4 1 3可以找到这样一种方法满足测量出4加仑水的方法。
花名册表示法:{a,b,c,d}
相等集合:两个集合包含相同的元素称为相等集合,如{1,3,3,5,5,5,5}和{1,3,5}是同一个集合
空集:不含任何元素的集合,空集的唯一元素是空集本身
单元素集:只有一个元素的集合
基数:令S为集合,S的基数记为|S|
幂集:给定集合S,S的幂集是集合S所有子集的集合,S的幂集记为
多重集:是一个元素的无序集,其中元素作为成员可以出现多于一次,如
一对一(one-to-one)或单射(injection)函数:当且仅当对于f的定义域中的所有a和b有f(a)=f(b)蕴含a=b。
映上(onto)或满射(subjection)函数:当且仅当对每个
一一对应(one-to-one correspondence)或双射(bijection)函数:既是一对一又是映上的。
下取整函数(floor):
康托尔-伯恩施坦定理:如果A和B是集合且
可计算与不可计算:如果存在某种编程语言写的计算机程序能计算该函数的值,则称为是可计算的,如果一个函数不是可计算的,就说是不可计算的。
0-1矩阵的并和交:矩阵的对应位进行并和交
布尔积:令
令A为0-1方阵,r为正整数,A的r次布尔幂是r个A的布尔积,记作
直接搜索:略
二分搜索:伪代码
xxxxxxxxxxprocedure binary_search(x:list, a:integer){ int i = 0; int j = len(x) - 1; int m = 0; while i<j { m := floor((i+j)/2) if x[m] < a then i:= m+1 else j := m } if x[m]=a then return i else return -1}冒泡排序和插入排序
朴素字符串匹配算法
安排讲座的贪婪算法:如果我们在每一步选择那个与巳选讲座相容的讲座中结束时间最早的讲 座,我们就能安排最多的讲座。
procedure schedule(
:讲座开始时间, :讲座结束时间) 根据结束时间对讲座排序,重新编号使得
for j := 1 to n
if 讲座j与S相容 then
return S{S是已经安排讲座的集合}
停机问题(halting problem):它询间是否存在一个过程(procedure) 能做这件事:该过程以一个计算机程序以及该程序的一个输入作为输入,并判断该程序在给定输入运行时是否最终能停止。
这个问题是没有解的
证明:假设停机问题有一个解,一个称为
编写一个过程的时候,它本身就表达为一个由字符构成的串,该串可以解释为一个比特序列。这意味着一个程序本身就可以当作数据使用。因此,一个程序可以作为另一个程序的输入,甚至是自身的输入。这样,H可以将一个程序P作为它的两个输入,即一个程序和该程序的输入。H应该可以判断当P给定其自身的副本作为输入时, P 是否会停机。
为了证明不存在过程H能够求解停机问题,我们构造一个简单过程K(P),如果H(P, P) 的输出是“无限循环”,即P在自身作为输入时会无限循环,那么让K(P)停机。如果H(P,P)的输出是“停机”,即P在自身作为输入时会停机,那么让K(P)无限循环。即K(P)做出和 H(P,P) 的输出相反结果。

现在假设把K作为K的输入。需要注意,如果H(K, K)的输出是“无限循环”,那么根据K的定义可以得出 K(K)停机。这意味着由H的定义, H(K, K)的输出是“停机”,这是一个矛盾。否则,如果 H(K, K) 的输出是“停机”,那么根据 K 的定义K(K)会无限循环,这意味着由H的定义, H(K, K) 的输出是“无限循环”。这也是一个矛盾。这样,H并不总能给出正确的答案。因此,没有这样的过程能解决停机问题。
定义:令f和g为从整数集或实数集到实数集的函数,如果存在常数C和k使得只要当x>k是就有
就可以说f(x)是O(g(x))的,读作f(x)是大Og(x)的。
当
如果
故
定理1:令
对于
对于
定理2:假定
定理3:假定
令f和g为从整数集合或实数集合到实数集合的函数,如果存在正常数
大O记号表示上界,大
令f和g为从整数集合或实数集合到实数集合的函数,如果
线性搜索算法的时间复杂度
算法中每次循环都要做两次比较,一次
二分搜索算法的时间复杂度
假定列表一共有
在算法的每一阶段,都要比较i和j(分别是当前待搜索列表的第一项和最后项的位置)来判断待搜索列表是否包含一个以上的元素。如果
第一阶段搜索限于含
冒泡算法的时间复杂度
在每一遍冒泡排序都连续比较相邻元素,必要时交换相邻元素。当第
插入排序的时间复杂度
插入排序把第j个元素插入到前j-1个已排好顺序的元素中的正确位置上。插入排序用线性搜索技术来做到这一点,依次比较第j个元素与后续各项,直到找到大于或等于这个元素的一项或者比较
普通的方阵乘法复杂度为
一般性的矩阵相乘,如
| 复杂度 | 术语 | 复杂度 | 术语 |
|---|---|---|---|
| 常量复杂度 | 多项式复杂度 | ||
| 对数复杂度 | 指数复杂度 | ||
| 线性复杂度 | 阶乘复杂度 | ||
| 线性对数复杂度 |
易解性:能用多项式最坏情形复杂度(或更优)的算法求解的问题称为易解的;
难解性:不能用最坏情形多项式时间复杂度的算法解决的问题;
P与NP:注意人们相信许多可解的问题具有这样的性质,即没有多项式最坏情形时间复杂度的算法能求解,但是一旦有了一个解答,却可以用多项式时间内来验证。能以多项式时间内验证解的问题称为属于 NP 类(易解的问题属于 P 类)。
NP完全问题 (NP-complete problem):具有这样的性质即只要其中任何一个问题能用一个多项式时间最坏情形算法来求解,那么NP类的所有问题都能用多项式时间最坏情形算法来求解。可满足性问题也是NP完全问题的一个例子。
P与NP问题(P versus NP problem):问NP(有可能在多项式时间内检验其解的一类问题)
是否等于P(一类易解的问题)。如果
用记号
除法算法:
如果
定理:令a和b为整数,并令m为正整数,则
定理:令m为正整数,整数a和b是模m同余的当且仅当存在整数
定理:令m为正整数,如果
推论:令m是正整数,令a和b是整数,则
并且
可以再
整数加法:
整数乘法:
构造b进制的算法:
procedure base b expansion (n,b:正整数且
) while return { 就是n的b进制展开式}
求解div和mod的算法(python)
xxxxxxxxxxdef divmod(a, d): q = 0 # q = a div d r = abs(a) # r = a mod d while r >= d: r = r - d q = q + 1 if a<0 and r > 0: r = d-r q = -(q+1) return q, r快速模指数运算:计算
为了计算
如计算
通过依次求出
procedure modular exponentiation(b:整数, n=
,m:正整数) for if then return x {x等于
}
代码(python) rapidexp[快速模指数运算].py
这里的很多内容在stein写的《Fouier analysis》这本书的狄利克雷定理那一章初等数论部分有,笔记见 数学.md #傅里叶分析 #狄利克雷定理。
埃拉托斯特尼筛法:用来寻找不超过一个给定整数的所有素数。不超过 100 的合数必定有一个不超过 10 的素因子。因为小于 10 的素数仅有 2 、 3 、5 和 7, 所以不超过 100 的素数就是这四个素数以及那些大于 1 且不超过 100 同时不能被 2 、 3 、5 和 7 之一整除的正整数。
梅森素数:当p为素数时,
素数定理:当x无限增长时,不超过x的素数个数与
哥德巴赫猜想:每个大于5的奇数n都是三个素数之和(或者是每个大于2的偶数是两个素数之和,两者等价)。
猜想(已被证明):存在无限多个可以写成
孪生素数猜想:孪生素数是指相差2的一对素数,诸如3和5、5和7、11和13、17和19、4967和4969。孪生素数猜想断定存在无限多对孪生素数。关于孪生素数已被证明的最好结果是有无限多对p和p+2 ,其中p是素数,p+2是素数或者是两个素数乘积(陈景润在1966 年证明)。设 P(n) 为命题:存在无限多对差值恰为n的素数对。孪生素数猜想就是命题P(2)为真。研究孪生素数猜想的数学家设计了一个稍微弱一点的猜想,称为有界间隔猜想,声称存在一个N 使得 P(N) 为真。
最大公约数:gcd(x,y) 最小公倍数:lcm(x,y)
定理:令a和b为正整数,则
procedure gcd(a,b:正整数)
while return x{gcd(a,b)是x}
贝组定理:如果a和b为正整数,则存在整数
扩展欧几里得算法求解a和b的贝组系数
设置
其中
定理:令m为正整数,令a,b和c为整数。如果
线性同余方程:同余方程的形式为
怎样求解线性同余方程
求解a模m的逆
对于
注意这里用到了gcd(a,m)=1的条件,则可以通过扩展欧几里得算法求出b,即贝组系数中的s。
定理(定理4.1):如果a和m为互素的整数且m>1,则a模m的逆存在。再者,这个模m的逆是唯一的。
证明:如果a和m互素,则
因此,s为a模m的逆。
假设有
中国剩余定理:令
有唯一的模
证明:令
以第一个方程为例,因为
举例:求解
使用构造法求解
首先令
从而得出 23 是方程组的最小正整数解。我们的结论是23是最小的正整数满足除以3时余2,除以 5 时余 3,除以 7 时余 2 。
使用反向替换算法计算
对于第一个方程x=3t+2,将x带入第二个方程可得
由于3和5互素,所以a肯定为5,b可以通过搜索小于a的值即小于5得到b=2,所以解得
假定
欲求 123 684 和 413 456 的和,根据中国剩余定理,每个小于 99 • 98 • 97 • 95 = 89403930的非负整数均可唯一地用该整数除以这四个模数的余数表示。例如,把123684表示为(33, 8, 9, 89),因为123684 mod 99=33,123684 mod 98=8, 123684 mod 97 =9 及 123684 mod 95=89。类似地,413456可表示为(32, 92, 42, 16) 。我们针对这些四元组而非直接针对这两个整数做运算,把四元组的对应分量相加,再按相应的模数压缩各分量。这样可得
要求出和,即(65,2,51,10)所表示的整数,需要求解同余方程组
求解结果为537140,程序代码如下:
xdef searchb(x0, a ,d_r): for i in range(0, a): if (x0 * i + d_r) % a == 0: return i
def rev_replace(m, r): x = [m[0], r[0]] for i in range(1, len(m)): a = m[i] # 由于m_j互素,所以a直接等于m[i] d_r = x[1] - r[i] b = searchb(x[0], a, d_r) x[1] += x[0] * b x[0] *= a return x[1]如果p为素数,a是一个不能被p整除的整数,则
再者,对每个整数a都有
可以利用费马小定理计算整数高次幂的模p余数
举例:计算
许多素数n都可以满足
需要说明的是,不能通过选择足够多的基数来区分素数与伪素数,因为有些正整数能通过满足gcd(b, n)=1的基数的所有测试。
一个正合数n如果对于所有满足gcd(b,n)=1的正整数b都有同余式
举例:整数561是卡米切尔数,首先561=
利用费马小定理可得到
有
模素数p的一个原根是
举例:判断2和3是否是模11的原根
在
反之计算3的幂次时,
假设p是一个素数,r是一个模p的原根,而a是介于(含)1和p-1之间的一个整数,如果
离散对数问题的输入是一个素数p、一个模p的原根 r 和一个正整数
在实践中,会用到了许多不同散列函数,最常用的散列函数之一是
其中m是可供使用的内存地址的数目。
举例:找出由散列函数h(k)=k mod 111分配给社会安全号为064212848和037149212的客户记录的内存地址
所以社会安全号为064212848的客户记录被分配到内存地址14,而社会安全号为 037149212 的客户记录被分配到内存地址65。
由于散列函数不是一对一的(因为很可能键值的数量大于内存地址数),所以有可能多个记录被分配到同一个内存地址。当这种情况发生时,就说出现了冲突。消解冲突的一个办法是使用散列函数分配但已被占用的地址后面第一个未占用的地址。
最常用的产生伪随机数的过程是线性同余法。我们选择4个整数:模数m、倍数a、增量c和种子
大部分计算机确实使用线性同余生成器来生成伪随机数,通常是使用增量
同余可用于检查数字串中的错误。在这样的字串中检错的一项常用技术就是在串的结尾处添加一个额外的数字。 这最后一个数字,或校验码,是用特定的函数来计算的。然后为了判定一个数字串是否正确,需要做一个检验看看这最后一位数字是否具有正确的值。如奇偶校验,通用产品代码和国际标准书号。
换位密码
举例:利用基于集合{1, 2, 3, 4}上的置换
加密明文消息 PIRAT E ATTACK
首先将明文信息分为4个字母一组,则为 PIRA TEAT TACK。要加密每个分组,我们把第一个字母移到第三位,把第二个字母移到第一位,把第三个字母移到第四位,再把第四个字母移到第二位。得到IAPR ETTA AKTC。
密码系统:是一个五元组
所有古典密码,包括移位密码和仿射密码,都是私钥密码系统的实例。在私钥密码系统中,一旦你知道加密密钥,你就能很快找到解密密钥。所以,知道如何用一个特定的密钥加密消息就能让你解密用该密钥加密的消息。现代的私钥密码如AES已经非常复杂,被认为可以很好地抵御密码分析。可是,它仍然具有共享安全通信密钥的特性。再者,为了更加安全,双方每次通信会话都需要用一个新密钥,这就需要一种能生成并安全分享密钥的方法。
为了避免每对希望安全通信的双方都需要共享密钥, 20 世纪 70 年代密码学家引入了公钥密码系统的概念。当使用这种密码系统时,知道怎样发送加密消息的人并不能解密消息。在这样的系统中,每个人都可以有一个众所周知的加密密钥。只有解密密钥是保密的,而且只有消息的预期接收人能解密。
尽管公钥密码系统的优势是保密通信的双方不需要交换密钥,但其劣势是加密解密都会非常耗时。对许多应用而言,这将使得公钥密码系统变得不实用。在这种情形下,通常是私钥密码系统取而代之。然而,公钥密码系统仍可以用于密钥的交换过程。
目前最常用的是RSA密码系统,在 RSA 密码系统中,每个人都有一个加密密钥
RSA加密:为了用特定的密钥(n, e)对消息加密,首先将明文消息M翻译成整数序列。为此,可以先将每个明文字母翻译成两位数,正如在移位密码中所做的翻译,只有一点不同 。 即对于字母A到J增加开始的0,所以 A 被翻译为00,B 为 01,…,J为 09。然后,将这些两位数连接起来构成数字串。接下来,将这个串再分成 2N 位数字等长的分组,这里 2N 是一个大偶数使得2N 位数字的整数 2525… 25 不超过n。(必要时,可以在明文消息后填充无意义的 X 使得最后一组的大小和其他分组一样)
经过这些步骤,我们已经将明文消息M翻译成了一个整数序列
RSA解密:已知解密密码d即e模
根据费马小定理,可得
且
由于gcd(p,q)=1,所以由中国剩余定理可得
举例:使用RSA系统及密钥(2537, 13)对消息STOP加密,注意2537=43*59,p=43和q=59是素数,并且
为了加密,先把STOP的字母翻译成等价的数字。然后按4位数字一组对这些数字分组(因为2525 <2537<252525),得到1819 1415,用下面的映射对每组加密
对加密消息 2081 2182进行解密,d=937是13模42·58=2436的逆(
翻译成英文字母为STOP。
为什么 RSA 密码系统适合作为公钥密码呢?首先,通过找寻两个各有300多位的大素数p和q,再找寻一个与
一个简单的RSA程序: simpleRSA[一个简单的RSA程序].py
全同态密码系统:是否有这样一个密码系统,允许在加密数据上做任何计算并能够产生由该非加密输入所得的非加密输出的加密形式。有了这样的密码系统,就不需要解密数据了,因为程序可以在远端系统上运行而不必解密输入或输出数据。
RSA是乘法同态的,而不是加法同态,所以是偏同态。
数学归纳法原理:为证明对所有的正整数n,P(n)为真,其中P(n)是一个命题函数,需要完成两个步骤:
基础步骤:证明命题P(1)为真
归纳步骤:证明对每个正整数,蕴含式
可以描述为:
举例:使用数学归纳法证明
基础步骤:P(0)=57能被57整除
归纳步骤:假设P(k)成立,对于P(k+1)有
显然能被57整除
举例:证明排讲座的算法(贪婪算法按照结束时间排)的最优
基础步骤:设贪婪算法在主讲座厅只安排一个讲座
归纳步骤:需要证明P(k)为真的假设下,当需要选择k+1个讲座时,贪婪算法也总是安排了最多的讲座。现在假定算法已经选择了k+1个讲座。要完成归纳步骤的第一步是:证明存在一个包含讲座
举例:有奇数个人站在一个院子里,彼此之间的距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人。利用数学归纳法证明:人群中至少有一个幸存者,即至少有一个人没有被馅饼攻击。
命题:当2n+1个人站在院中,彼此之间距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人时,至少存在一个幸存者。为了证明此结果,将证明对所有的正整数n,P(n)为真。这是可行的,因为当n取遍所有正整数时,2n+1则取遍了所有大于等于3的奇数。注意,一个人的馅饼战斗是不存在的,因为不存在另外一个人成为他攻击的对象。
基础步骤:n=1时一共有3个人站在院子中,彼此之间距离不同,假设距离最近的两个人是A和 B,而C是第三个人。因为三人中两两之间的距离是不同的,A与C之间的距离以及B与C之间的距离都不同于且大于A与B之间的距离,因此,C不会受到馅饼的攻击。这表明,三个人中至少有一个人不会受到馅饼的攻击。
归纳步骤:假定P(k)为真,即当2k+1个人站在院中,彼此之间距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人时,至少存在一个幸存者。当P(k+1)时,有2k+3个人站在院中,假设A和B是靠得最近的两个人,所以抛击时A和B相互抛击。分成两种情况
(1)有人向A和B抛击:由于有人向A和B抛击,并且A和B相互抛击,所以A和B加起来至少会受到3个馅饼的抛击,那就代表至少有一个人没有被抛击(2k+1个人至少需要2k+1个馅饼才能全部抛击,现在最多只有2k个馅饼);
(2)没人向A和B抛击:这样就退化成P(k)的情况,即至少有一个人不会受到馅饼的攻击。
综上,P(k+1)时,至少有一个人不会受到馅饼的攻击
在强归纳法中,归纳步骤需要证明的是:如果对所有不超过k的正整数而言,P(j)为真,那么 P(k+1)也为真,即关于归纳假设,假定对
强归纳法:为证明对所有的正整数n,P(n)为真,其中P(n)是一个命题函数,需要完成两个步骤:
基础步骤:证明命题P(1)为真
归纳步骤:证明对所有正整数k来说,蕴含式
强归纳法有时也称为数学归纳法第二原理,或称为完全归纳法。当使用“完全归纳法”这一术语时,数学归纳法原理就称为不完全归纳法。
利用强归纳法可以证明出数学归纳法不能轻易证明出来的结论
举例:设我们能到达无限高梯子的第1个和第2个阶梯,且知道如果我们能到达某个阶梯,那么就能到达高出两阶的那个阶梯。我们能用数学归纳法证明“我们能到达每一个阶梯”吗?我们又能用强归纳法证明“我们能到达每一个阶梯”吗?(下面的证明只关注归纳步骤)
数学归纳法:归纳假设是命题“我们能到达第k个阶梯”。为了能完成归纳步骤,需要证明:如果假定归纳假设是对正整数k而言的,也就是说,如果假定我们能够到达第k个阶梯,那么就能证明我们能到达第k+1个阶梯。然而,并没有明显的方式来完成这一归纳步骤,这是因为从所给信息来看,我们不知道是否能从第k个阶梯到达第k+1个阶梯。毕竟我们只知道“如果我们能到达一个阶梯,则我们能到达高出两阶的那个阶梯”。
强归纳法:归纳假设是命题“我们能到达前k个阶梯中的每个阶梯”。为了能完成归纳步骤,需要证明:在归纳假设为真的情况下,即如果我们能到达前k个阶梯中的每个阶梯,那么我们就能到达第k+1个阶梯。已经证明了我们能到达第2个阶梯。这里只需注意:只要k>2,那么就可从第k-1个阶梯到达第k+1个阶梯,因为知道我们可以从某个阶梯到达高出两阶的那个阶梯。这样就由强归纳法完成了归纳步骤。
只要对强归纳法稍加改变,就可以处理更为广泛的一类问题。特别是在强归纳步骤只对大于某个特定的整数有效时,可以改变强归纳法来适应这种情况。设b是一个固定的整数,而j是一个固定的正整数。如果能完成如下两个步骤,那么强归纳法就可以断言:对所有
举例:若n是大于1的整数,则n可以写成素数之积
基础步骤:P(2)为真,因为2可以写成一个素数之积,即它自身。
归纳步骤:假定对所有满足
举例:考虑一种游戏,其中两名选手轮流从两堆火柴中的一堆取出任意正整数的火柴。取走最后一根火柴的选手获胜。证明:如果开始时两堆火柴的数目相同,则第二名选手总是可以 保证获胜。
基础步骤:当n=1时,先拿火柴的选手只有一种选择,从某一堆中取走一根火柴,剩下一堆只有一根,第二名选手可以取走这根火柴而获胜。
归纳步骤:假设对所有
定理:具有n条边的简单多边形能够被三角形化成n-2个三角形,其中
使用强归纳法证明该定理时,需要用到下面的引理(引理证明略)
引理:每个简单的至少四边的多边形都存在一条内部对角线。
基础步骤:T(3)为真,因为具有三条边的多边形是一个三角形。不需要对一个三角形加入任何对角线。该三角形已经被三角形化了,即它自身。
归纳步骤:关于归纳假设,假定对所有
良序性公理断言:任意一个非空的非负整数集合都有最小元素。我们将会看到,良序性公理是怎样直接应用于证明中的。此外,可以证明:良序性公理、数学归纳法原理以及强归纳法之间是等价的。
举例:用良序性证明整除算法。回忆一下,整除算法说:若a是整数且d是正整数,则存在唯一的整数q和r满足
设S是形如a—dq的非负整数的集合,其中q是整数。这个集合非空,因为-dq可以任意大(取q是绝对值很大的负整数)。根据良序性,S有最小元
唯一性的证明:假设存在
定理(拉梅定理):设a和b是满足
证明:当使用欧几里得算法求满足
这里为了求
因此,
基础步骤:证明对于递归定义的基础步骤所规定的属于该集合的所有元素来说,结果成立。 递归步骤:证明如果对于定义的递归步骤中用来构造新元素的每个元素来说命题为真,则对于这些新的元素来说结果成立。
举例:可以定义关于T、F、s命题变量以及集合
基础步骤:公式T、F和s每个都不包含括号,所以显然它们含有相等个数的左括号和右括号。
递归步骤:假设p和q都是各自含有相等个数的左括号和右括号的合式公式。换句话说,如果
递归地定义满二叉树T的高度
基础步骤:只含有树根r的满二叉树T的高度是
递归步骤:如果
定理:如果T是满二叉树,则
基础步骤:对于只含有树根r的满二叉树来说,结果为真,因为n(T)=1并且h(T)=0,所以
归纳步骤:对于归纳假设,假定当
略(原书315页)
定义:若一个算法通过把问题归约到带更小输入的相同问题的实例来解决原来的问题,则称这个算法是递归的。
递归计算最大公约数
procedure gcd(a,b:非负整数且a<b) if a=0 then return b else return gcd (b mod a, a) {输出是gcd(a, b)}
递归模指数的算法
procedure mpower(b, n, m:整数且
、 、 ) if n=0 then return 1 else return b*mpower(b, n-1, m) mod m
{输出是
}
分类讨论n奇偶性
procedure mpowerbetter(b, n, m:整数且
、 、 ) if n=0 then return 1 else if n是偶数 then
return
mod m else
return [(
mod m) (b mod m)]mod m {输出是
}
上述算法的python代码见 recursive1[递归计算的一些实例].py
归并排序首先通过不断地把表一分为二来把表分成单个的元素,用归并排序算法排序每个子表,然后合并这两个子表。
递归归并排序
procedure mergesort (
) if n>1 then {现在L中的元素以非降序排列}
归并两个表
procedure merge(
, :已排序的表) L := 空表 while 和 都非空 从 和 的第一元素中较小的元素所在的表中删除这个元素并且把这个元素放到L的左端 if 删除这个元素导致一个表为空 then 从另一个表中删除所有元素并且把这些元素附加到L的后面 return L{L是元素按照递增顺序排列的已归并的表}
python代码: mergesort[归并排序].py
归并排序的时间复杂度为
定义:若当对一个程序或程序段S的输入值来说初始断言p为真时,就有对S的输出值来说终结断言q为真,则说S是相对于p和q部分正确的。记号
合成规则:
定理:如果k+1个或更多的物体放入k个盒子,那么至少有一个盒子包含了2个或更多的物体。
推论:一个从有k+1甚至更多个元素的集合到k个元素的集合的函数f不是一对一函数
证明:设函数f陪域中的每一个元素y都有一个盒子,包含了定义域中满足f(x)=y的x。因为定义域有k+1或者更多个元素,而陪域只有k个元素,所以由鸽巢原理可知这些盒子中有一个包含了定义域中2个或者更多的x元素,这说明f不是一对一函数。
举例:对每个整数n,存在一个数是n的倍数且在它的十进制表示中只出现0和1
令n是正整数,考虑n个整数1,11,111,...,11
定理:如果N个物体放入k个盒子,那么至少有一个盒子包含了至少
举例:在100个人中至少有
举例:证明在不超过2n的任意n+1个正整数中一定存在一个正整数被另一个正整数整除
把n+1个整数
定理:每个由
证明:令
假定没有长为n+1的递增或递减子序列,那么
拉姆齐数
已知R(3,3)=6,R(4,4)=18,对于拉姆齐数,当
一些性质:R(2,n) = n,R(m,n)=R(n, m)
排列数:
组合数:
定理:设x和y是变量,n时非负整数,那么
推论:设n为非负整数,那么
推论:设n为非负整数,那么
定理:设n和k是满足
定理(范德蒙德恒等式):设m,n和r是非负整数,其中r不超过m或n,那么
定理:设n和r是非负整数,
定理:具有n个物体的集合允许重复的r排列数是
定理:n个元素的集合中允许重复的r组合有C(n+r-1,r)=C(n+r-1,n-1)个。
举例:方程
这个解对应从一个三元素集合中选11个元素的方式,假设这里有11个元素(它们加起来就是11),现在要添加2个分割线将它们分为三个集合,所以可以假设一共有13个元素,挑两个位置放分割线,所以一共是C(13, 2)=C(n+r-1, n-1)=78。
给变量加上限制如
定理:设类型1的相同的物体有
举例:重新排列单词SUCCESS中的字母能构成多少个不同的串
计算:
后续内容不过多介绍
生成n个最小正整数的排列,然后用对应的元素替换这些整数。已经建立了许多不同的算法来生成这个集合的n!个排列。我们将要描述的算法是以{1,2,3,...,n}的排列集合上的字典顺序为基础的。按照这个顺序,如果对于某个k,
举例:在362541后面按照字典顺序下一个最大的排列是什么?
解:使得
按字典顺序生成下一个最大排列
procedure next_permutation(
: {1,2,...,n}的排列,不等于n...1) j := n—1 while j := j—1 {j是使得 的最大下标} k := n while k := k-1 { 是在 右边大于 的最小整数} 交换 和 r := n s := j + 1 while r>s 交换 和 r := r-1 s := s+1 {这把在第j位后边的排列尾部按递增顺序放置} {现在 是下一个排列}
生成排列的python代码: gen_permutation[生成排列].py
可以利用一个集合(包括n个元素)的子集与n位比特串之间的对应关系
举例:找出在1000100111后面的下一个最大的比特串
解:相当于
如果要求房间内至少有2个人有相同生日的概率大于1/2,那么所需的最少人数是多少?
为了找到房间内n个人至少2个人生日相同的概率,可以一个一个的来看,先看第一个人进入房间,那么他肯定不会与别人生日相同,第二个人进入房间,生日不相同的概率是365/366,第三个人生日互不相同的概率为364/366,第j个人进入房间后与其他人生日都不相同的概率为(366-(j-1))/366,假设生日相互独立,那么j个人生日互不相同的概率为:
则至少有两个人生日相同的概率为
另外一种算法:先算所有人生日都不相同,假设有n个人,一共有366个生日,所以n个人一共有
那么至少有两个人生日相等的概率为1-
生日问题的仿真: birthday[生日问题].py
举例:散列函数碰撞的概率
令m为有效地址的个数,关键字的个数为n个(k1,k2,...,kn),则n个关键字被映射到不同地址的概率为
定理:如果k是一个整数,k≥2,那么
定理(比安内梅公式):如果X和Y是样本空间S上两个独立的随机变量,那么V(X+Y)=V(X)+V(Y),这里的V(X)表示X的方差。对于正整数n,
定理(切比雪夫不等式):设X是在样本空间S上的概率函数为p的随机变量。如果r是一个正实数,那么
证明:设A是事件A={s∈S||X(s)-E(X)|≥r},注意到
这个表达式中的第二个和是非负的,因为它的每个被加数是非负的,又因为对于每个元素s,有
所以
举例:汉诺塔问题,将n个盘子从A处搬到B处,还有C处可作为中间点暂存盘子,在A、B、C三处都只能允许从上到下按照从小到大的顺序排列。问总共需要多少次操作完成目标。
使用递推思想,将n-1个盘子从A处搬到C处(B处作为中间点)需要
汉诺塔问题的python代码如下:
xxxxxxxxxxdef hanoi(n, f, m, t): # f:起点 m:中间 t:终点 if n == 1: print(f"{f} -> {t}") return hanoi(n-1, f, t, m) # 将n-1个盘子从A搬到C,中间用B作为中间节点 print(f"{f} -> {t}") # 将A中最后一个盘子放到B hanoi(n-1, m, f, t) # 将放在C上的n-1个盘子搬到B上,A作为中间节点if __name__ == "__main__": hanoi(3, 'A', 'C', 'B') # 'A' 借助'C' 将盘子转移到 'B'
举例:对于不含2个连续0的n位比特串的个数,找出递推关系和初始条件。有多少个这样的5位比特串?
当比特串以1结尾时有
举例:编码字的枚举,如果一个十进制数字串包含偶数个0,计算机系统就把它作为一个有效的编码字。例如,1230407869是有效的,而120987045608不是有效的。设
注意
第一种情况,无效字符串加了0就可以得到n位有效的字符串,n-1位的字符串一共有
第二种情况,有效字符串加了非0,一共有
所以
还可以通过定义一个无效字符串个数
动态规划实例:对于安排讲座的问题,现在我们的目标不是安排尽可能多的讲座,而是尽可能多地合并已规划讲座的参与者。设有n个讲座,讲座j开始于时间
我们用T(j)来表示由一个优化调度得到的前j场讲座的最大参与总数,T(n)就是一个优化调度得到的对于所有n个讲座的最大参与总数。首先将讲座结束时间升序排序。此后,我们重新编号讲座,
为了设计一个解决这个问题的动态规划算法,我们首先提出一个关键的递推关系。首先注意j≤n。对于前j个讲座,有两种可能的优化调度(注意,我们已经将n个讲座按结束时间升序排序)(i)讲座j属于优化调度;(ii)它不属于。
情况(i):我们知道讲座p(j)+1,...,j-1不可能属于这个规划,因为这些讲座与讲座j都不相容。进一步,在优化调度中的其他讲座必定包括了讲座1,2,...,p(j)的一个优化调度。因为如果对于1,2,...,p(j)有更好的优化调度,通过加上讲座j,我们将得一个比总体
优化调度更好的规划。所以,在情况(i)下,
情况(ii):当讲座j不属于一个优化调度时,讲座1,2,...,j的优化调度就与讲座1,2,...,j-1的一样。因此,在情况(ii)下,T(j)=T(j-1)。结合情况(i)和(ii),可得到一个递推关系:
调度讲座的动态规划算法
Procedure Maximum_Attendees(
:讲座的开始时间; :讲座的结束时间; :讲座的参与人数) 将讲座按结束时间排序,并重新标记讲座,保证
for j:= 1 to n if 没有任务i(i<j)与任务j相兼容; p(j)=0 else p(j) := max{i|i<j 并且任务i与任务j相兼容} T(0):=0 for j:= 1 to n T(j) := max( + T(p(j)), T(j-1)) return T(n) {T(n)是最大的参与人数}
一个常系数的k阶线性齐次递推关系是形如
定理:设
定理:设
定理:如果{
的一个解。
分治递推关系:f(n)=af(n/b)+g(n)
二分搜索:f(n)=f(n/2)+2
归并排序:f(n)=2f(n/2)+n
举例:整数的快速乘法,有一种快速的乘法算法把每个2n位的二进制整数分成两块,每块n位。然后,原来2n位的二进制整数的乘法被分解成3个n位二进制数的乘法,还要加上移位和加法。
假设a和b是两个整数的2n位的二进制表达式(为了使它们等长,如果需要,可以在这些表达式前面加上若干个0)。令
令
其中
快速整数乘法算法是基于恒等式
分治递推关系:f(2n)=3f(n)+C(n)
定理:设f是满足递推关系 f(n)=af(n/b)+c的增函数,其中n被b整除,a≥1,b是大于1的整数,c是一个正实数,那么
而且,当
定理(主定理):设f是满足递推关系
的增函数,其中
最近对问题(不多赘述)
实数序列
定理:令
定理(广义二项式定理):设x是实数,|x|<1,u是实数,那么
有用的生成函数表见P473-474页。
示例:求
上述限制解的个数为
示例:使用生成函数求出从n类不同的物体中选择r个物体并且每类物体至少选1个的方式数。
因为我们需要每类物体至少选1个,所以这n个类中的每类物体都对序列{
根据广义多项式有
举例:求递推关系
设
所以
举例:使用生成函数证明,n为正整数
首先C(2n,n)是
在这个展开式中,
即
设
如果不具有n个性质
由容斥原理有
举例:方程
(1)使用容斥定理,令解的性质
其中N表示解的总数即C(3+11-1,2)=78(详细分析见 有重复的组合)
N(P1)=(具有x1≥4的解数)=C(3+7-1, 2)=36
其它以此类推。最后结果为6
(2)由于
定理:设m和n是正整数,满足
个从m元素集合到n元素集合的映上函数。
从m元素集合到n元素集合的映上函数是这样一种对应方式:它把定义域中的m个元素分配到n个不可辨别的盒子中,使得每个盒子都不是空的,然后将陪域中的n个元素中的每一个元素都与一个盒子相对应。这意味着从具有m个元素的集合到具有n个元素的集合的映上函数的个数,等于把m个可辨别的物体分配到n个不可辨别的盒子中,使得每个盒子都不空时的方法数乘以具有n个元素的集合的排列数。因此,从m个元素的集合到n个元素的集合的映上函数的个数为 n!S(m,s),其中 S(m,n)是6.5节中定义的第二类斯特林数。
举例:把5项工作分给4个不同的雇员,如果每个雇员至少分配1项工作,问有多少种方式?
由定理可知:共有
错位排列指将元素随机打乱并保证没有一个元素在原始位置。
定理:n元素集合的错位排列数为
证明:如果排列保持元素i不变,就设排列有性质
定义:设A和B是集合,一个从A到B的二元关系是A×B的子集。
定义:集合A上的关系是从A到A的关系
设集合A = {1,2,3,4},那么R={(1,1),(1,2),(2, 1),(2,2),(3,4),(4,1),(4,4)}就是一种关系
定义:若对每个元素a∈A,有(a,a)∈R,那么定义在集合A上的关系是自反的。
定义:对于任意a,b∈A,若只要(a,b)∈R就有(b,a)∈R,则称定义在集合A上的关系R为对称的。对于任意a,b∈A,若(a,b)∈R且(b,a)∈R,一定有a=b,则称定义在集合A上的关系R为反对称的。
定义:若对于任意a,b,c∈A,(a,b)∈R并且(b,c)∈R则(a,c)属于R,那么定义在集合A上的关系R称为传递的。
定义:设R是从集合A到B的关系,S是集合B到C的关系,R和S的合成是由有序对(a,c)的集合构成的关系,其中a∈A,c∈C,并且存在一个b∈B的元素,使得(a,b)∈R且(b,c)∈S,用
定义:设R是集合A上的关系,R的n次幂
定理:集合A上的关系R是传递的,当且仅当对n=1,2,3,...有
设
当n元组的某个域的值能够确定这个n元组时,n元关系的这个域就叫作主键。这就是说,当关系中没有两个n元组在这个域有相同的值时,这个域就是主键。在一个n元关系中,域的组合也可以唯一地标识n元组。当一组域的值确定一个关系中的n元组时,这些域的笛卡儿积就叫作复合主键。
定义:设R是一个n元关系,C是R中元素可能满足的一个条件。那么选择运算符
定义:投影
定义:连接运算符
如果将数据挖掘的场景局限在超市事务上,那么
事务:客户在访问商店期间购买的一些商品的集合,如{牛奶、鸡蛋、面包}
项集:商店里的每一件商品称为项,项的集合称为项集,k项集是一个包含恰好k项的项集。
定义:在事务集合T={
对于特定的应用,会指定一个支持度阈值s。频繁项集挖掘是寻找支持度大于等于s的项集I的过程,这些项集被称为频繁项集。
举例:一个事务集如下

对于苹果而言,一共出现在了8个事务中的5个,所以
关联规则的强度是根据它的支持度(包含I和J的事务频率)以及置信度(包含J时也包含I的事务频率)来衡量的。
定义:若I和J是事务集T的子集,则
和
关联规则
在上面的例子中,关联规则的支持度是 σ({苹果酒,甜甜圈} U {苹果})/|T|。因为σ{苹果酒,甜甜圈}U{苹果})=σ{苹果酒,甜甜圈,苹果})= 3,|T|=8, 可得这条规则的支持度是 3/8=0.375。 该规则的置信度是σ({苹果酒,甜甜圈} U {苹果})/σ({苹果酒,甜甜圈}) = 3/4=0.75。
关系矩阵:关系R可以用矩阵M表示,其中
对于关系的合成
定义:设R是集合A上的关系,若存在关系R的具有性质P的闭包,则此闭包是集合A上包含R的具有性质P的关系S,并且S是每一个包含R的具有性质P的A×A的子集。
在有向图G中,从a到b的一条路径是图G中一条或多条边的序列
定义:在有向图G中,从a到b的一条路径是图G中一条或多条边的序列(
定理:设R是集合A上的关系,从a到b存在一条长为n(n为正整数)的路径,当且仅当(a,b)∈
使用数学归纳法证明,当n=1时,(a,b)∈R,从a到b有一条长为1的路径
假设对于正整数n成立,从a到b存在一条长为n+1的路径,当且仅当存在元素c∈A使得从a到c存在一条长为1的路径,即(a,c)∈R,以及一条从c到b的长为n的路径,即(c,b)∈
定义:设R是集合A上的关系,连通性关系
因为
定理:关系R的传递闭包等于连通性关系
定理:设
计算传递闭包的过程
procedure transitive_closure(M: n×n的0-1矩阵)
A:=M
B:=A
for i:= 2 to n
A := A
M B := B
A return B {B是表示
的0-1矩阵}
该算法的运算复杂度为O(
沃舍尔算法的基础是构造一系列的0-1矩阵。这些矩阵是
举例:假设
对于
从
第一种类型的路径存在当且仅当
沃舍尔算法
procedure Warshall(M: n×n的0-1矩阵)
W := M
for k := 1 to n
for i := 1 to n
for j := 1 to n
:= return W {W=[
]是 }
该算法的时间复杂度为
定义:等价关系:自反的、对称的和传递的
定义:如果两个元素a和b由于等价关系而相关联,则称它们是等价的。记法a~b通常用来表示对于某个特定的等价关系来说,a和b是等价的元素。
定义:偏序:自反的,反对称的和传递的。集合S和定义在其上的偏序R称为偏序集,记作(S,R)。
关键词:哈塞图、极大元、极小元、最大元、最小元、拓扑排序、格
偏序不太清楚有什么用。拓扑排序好像可以用来排任务
每条边都连接两个不同的顶点且没有两条不同的边连接一对相同顶点的图称为简单图,可能会有多重边连接同一对顶点的图称为多重图。
定义:若u和v是无向图G中的一条边e的端点,则称两个顶点u和v在G里邻接(或相邻)。这样的边e称为关联顶点u和v,也可以说边e连接u和v。
定义:图G=(V,E)中,顶点v的所有相邻顶点的集合,记作N(v),称为顶点v的邻居。若A是V的子集,我们用N(A)表示图G中至少和A中一个顶点相邻的所有顶点的集合,所以
定义:在无向图中,顶点的度是与该顶点相关联的边的数目,例外的情形是,顶点上的环为顶点的度做出双倍贡献。顶点v的度表示成deg(v)。
定理(握手定理):设G=(V,E)是有m条边的无向图,则
定理:无向图有偶数个度为奇数的顶点。
定义:当(u,v)是带有有向边的图G的边时,说u邻接到v,或者说v从u邻接。顶点u称为(u,v)的起点,v称为(u,v)的终点,环的起点和终点是相同的。
定义:在带有有向边的图里,顶点v的入度,记作
定理:设G=(V,E)是带有向边的图,每条边都有一个起点和终点,于是
定义:若把简单图G的顶点集分成两个不相交的非空集合
定理:一个简单图是二分图,当且仅当能够对图中的每个顶点赋予两种不同的颜色,并使得没有两个相邻的顶点被赋予相同的颜色。
完全二分图

举例:假设1个组中有m个员工,需要完成n种不同的工作,其中m≥n。每个员工都受过相关培训,能够完成这n个工作中的1种或多种。我们希望可以为每个员工分配一个工作。为了完成这个任务,我们可以使用图为员工的能力建模。用顶点表示每一个员工和每一个工作,对于每个员工,在表示他和他受过培训的工作的顶点之间建立一条边。注意,这个图的顶点集合被划分为两个不相交的集合,员工的集合和工作的集合,而且每条边都连接着一个员工和一个工作。因此,这个图是二分图,划分是(E,J),其中E是员工的集合,J是工作的集合。下面我们考虑两种不同的场景。
第一,假设1组有4个员工:Alvarez、Berkowitz、Chen和Davis。假设完成项目1需要做4个工作:需求、架构、实现和测试。假设Alvarez受过需求和测试的培训;Berkowit受过架构、实现和测试的培训;Chen受过需求、架构和实现的培训;Davis仅受过需求的培训。 第二,假设这个组中第2个小组也有4个员工:Washington、Xuan、Ybarra和Ziegler。假设完成项目2也需要和完成项目1一样完成相同的4种工作。假设Washington受过架构的培训;Xuan受过需求、实现和测试的培训;Ybarra受过架构的培训;Ziegler受过需求、架构和测试的培训。 为了完成项目1,我们必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。如图所示(其中蓝色线表示工作分配),我们可以通过给Alvarez分配测试、给Berkowitz分配实现、给Chen分配架构和给Davis分配需求来完成这个要求。

为了完成项目1,我们必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。如图(a)所示(其中蓝色线表示工作分配),我们可以通过给Alvarez分配测试、给Berkowitz分配实现、给Chen分配架构和给Davis分配需求来完成这个要求。
为了完成项目2,我们也必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。但是这是不可能的,因为只有Xuan和Ziegler两个员工至少受过需求、实现和测试这3个工作之一的培训。因此,没有办法为这3个工作分配3个不同的员工且每个工作都能分配一个受过相关培训的员工。
寻找一种把工作分配给员工的方法可以视为在图模型中寻求匹配,其中,在简单图G=(V,E)中的一个匹配M就是图中边集E的子集,该子集中没有两条边关联相同的顶点。换句话说,匹配是边的子集,假设{s,t}和{u,v}是匹配中不同的边,那么s、t、u和v是不同的顶点。若一个顶点是匹配M中的一条边的端点,则称该顶点在M中被匹配;否则称为未被匹配。包含最多边数的一个匹配称为最大匹配。在二分图G=(V,E)中的一个匹配M,其划分为(
定理(霍尔婚姻定理):带有二部划分(
先来证明必要条件,假设从
充分性通过强归纳法证明,比较困难,详见P580页。
举例:并行计算的互连网络,采用并行处理时,一个处理器需要另一个处理器产生的输出。因此这些处理器需要互连。
最简单却又最昂贵的网络互连处理器,在每对处理器之间有一个双向连接。当有n个处理器时,这样的网络表示成n个顶点上的完全图
另一方面,互连n个处理器的最简单方式或许是使用称为线性阵列的排列方式。除了
栅格网络(或二维阵列)是一种通用的互连网络。在这样的网络中,处理器个数是一个完全平方数,比方说n=

超立方体是互连网络的一个重要类型。在这样的网络中,处理器个数是2的幂,

定义:图G=(V,E)的子图是图H=(W,F),其中
定义:令G=(V,E)是一个简单图。图(W,F)是由顶点集V的子集W导出的子图,其中边集F包含E中的一条边当且仅当这条边的两个端点都在W中。
定义:两个简单图
有时,两个图具有完全相同的形式,从某种意义上就是两个图的顶点之间存在着一一对应,这个对应保持边的对应关系。在这种情形下,就说这两个图是同构的。
邻接表:给出了与图中每个顶点相邻的顶点。
邻接矩阵:若图G=(V(顶点),E(边))的邻接矩阵是
关联矩阵:若图G=(V,E)的关联矩阵是
定义:设
换句话说,当两个简单图同构时,两个图的顶点之间具有保持相邻关系的一一对应。简单图的同构是一个等价关系。
判断两个简单图是否同构常常是一件困难的事情。在两个带有n个顶点的简单图的顶点集之间有n!种可能的一一对应。若n太大,则通过检验每一种对应来看它是否保持相邻关系是不可行的。 有时说明两个图不同构并不困难。特别是,如果能找到某个属性,两个图中只有一个图具有这个属性,但该属性应该在同构时保持,就可以说这两个图不同构。这种在图的同构中保持的属性称为图形不变量。例如,同构的简单图必须具有相同的顶点数,因为在这些图的顶点集之间有一一对应。
举例:顶点数、边数以及顶点的度都是在同构下的不变量。若两个简单图的这些量有任何不同,则这两个图就不是同构的。不过,当这些不变量都相同时,也不一定意味着两个图是同构的。目前还没有已知的用来判定简单图是否同构的不变量集。
举例:判断下面的图是否同构

首先图G和H有相同的顶点数、边数以及顶点的度,然而G和H不同构。以G中的a点为例,对应了H中的t、u、x、y,而这四个顶点都与deg为2的顶点相邻,而G中的a点只与deg为3的顶点相邻。
举例:判断图G和H是否是同构的

G和H有着相同的顶点数、边数以及顶点的度,可以判断可能同构,再观察G中
为了确定f是否保持边,可以检查G和H的邻接矩阵(此处的H矩阵使用G中的对应顶点的像来标记行和列),即此时H中的顶点为(
可以看到
NAUTY是一种用于测试图同构的最佳使用算法。
定义:设n是非负整数且G是无向图。在G中从u到v的长度为n的通路是G的n条边
定义:设n是非负整数且G是有向图。在G中从u到v的长度为n的通路是G的边的序列
定理:在连通无向图的每一对顶点之间都存在简单通路
有时删除图中的一个顶点和它所关联的边,就产生比原图具有更多连通分支的子图。把这样的顶点称为割点(或关节点)。从连通图里删除割点,就产生不连通的子图。同理,如果删除一条边,就产生比原图具有更多连通分支的子图,这条边就称为割边或桥。注意,在表示计算机网络的图中,割点和割边表示了最重要的路由器和最重要的链路,为了使所有的计算机可以通信,它们不能发生故障。
并不是所有的图都有割点,如完全连通图
我们定义非完全图的点连通度为点割集中最小的顶点数,记作
若
与顶点类似,也有边割集和边连通度(用λ(G)表示),若G是不连通的,则λ(G)=0。若G是只含有1个顶点的图,我们也定义λ(G)=0。由此可得,若G是含有n个顶点的图,则0≤λ(G)≤n-1。G 是含有n个顶点的图,λ(G)=n-1当且仅当G=
对于所有的图而言,存在下面这个不等式
定义:若对于有向图中的任意顶点a和b,都有从a到b和从b到a的通路,则该图是强连通的。
定义:若在有向图的基本无向图中,任何两个顶点之间都有通路,则该有向图是弱连通的。
有向图G的子图是强连通的,但不包含在更大的强连通子图中,即极大强连通子图,可称为 G 的强连通分支或强分支。注意,若a和b是有向图中的两个顶点,它们的强连通分支或者相同或者不相交。
简单图的一个有用的同构不变量是长度为k的简单回路的存在性,其中k是大于2的正整数。
举例:判定图G和图H是否是同构的

G和H都具有6个顶点和8条边,各自具有4个度为3的顶点和2个度为2的顶点。所以对两个图来说,这3个不变量(顶点数、边数以及顶点度)都是相同的。但是H有长度为3的简单回路,即
定理:设G是一个图,该图的邻接矩阵A相对于图中的顶点顺序
该定理可以用来求出在图的两个顶点之间的最短通路的长度,还可以用来判定图是否连通。
定义:图G中的欧拉回路是包含G的每一条边的简单回路。图G中的欧拉通路是包含G的每一条边的简单通路。
定理:含有至少2个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都为偶数。
构造欧拉回路
procedure Euler(G:所有顶点的度都为偶数的连通多重图)
circuit := 从G中任选的顶点开始,连续地加入边所形成的回到该顶点的回路 H := 删除这条回路的边之后的G while H还有边 subcircuit := 在既是H的顶点也是circuit的边的端点处开始的H的一条回路 H := 删除subcircuit的边和所有孤立点之后的H circuit := 在适当顶点上插入subcircuit之后的circuit return circuit {circuit是欧拉回路}
定理:连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有2个度为奇数的顶点。
定义:经过图G中每一个顶点恰好一次的简单通路称为哈密顿通路,经过图G中每一个顶点恰好一次的简单回路称为哈密顿回路。即,在图G=(V,E)中,若V={
带有度为1的顶点的图没有哈密顿回路,因为在哈密顿回路中每个顶点都关联回路中的两条边。另外,若图中有度为2的顶点,则关联这个顶点的两条边属于任意一条哈密顿回路。此外注意,当构造哈密顿回路且该回路经过某一个顶点时,除了回路所用到的两条边以外,这个顶点所关联的其他所有边不用再考虑。而且,哈密顿回路不能包含更小的回路。
定理(狄拉克定理):如果G是有n个顶点的简单图,其中n≥3,并且G中每个顶点的度都至少为n/2,则G有哈密顿回路。
定理(欧尔定理):如果G是有n个顶点的简单图,其中n≥3,并且对于G中每一对不相邻的顶点u和v来说,都有deg(u)+deg(v)≥n,则G有哈密顿回路。
已知最好的求一个图哈密顿回路或判定这样的回路不存在的算法具有指数级的最坏情形时间复杂度(相对于图的顶点数来说)。
格雷码使得相邻的码具有恰好相差一位。可以这样找出格雷码:以下述方式列出所有长度为n的比特串,使得每一个串与前一个串恰好相差一位,而且最后一个串与第一个串恰好相差一位。可以用n立方体
![]() | ![]() |
|---|
左边表示
迪杰斯特拉算法
procedure Dijkstra(G:所有权都为正数的带权连通简单图)
{G带有顶点a=
, ,..., =z和权 ,其中若{ }不是G的边,则 } for i := 1 to n L(a) := 0 S := {现在初始化标记,使得a的标记为0而所有其余标记为∞,S是空集合} while z S u := a不属于S的L(u)最小的一个顶点 S := S U {u} for 所有不属于S的顶点 v if L(u)+w(u,v) < L(v) then L(v) := L(u)+w(u, v) {这样就给S中添加带最小标记的顶点,并且更新不在S中的顶点的标记) return L(z) {L(z)=从a到z的最短通路的长度}
python代码: djikstra[迪杰斯特拉算法].py
定理:迪克斯特拉算法使用
弗洛伊德算法
procedure Floyd(G:带权简单图) {G有顶点
, ,..., 和权 ,其中若( )不是边,则 } for i := 1 to n for j := 1 to n for i := 1 to n for j := 1 to n for k := 1 to n if + < then = + return { 是在 与 之间的最短通路的长度,1≤i≤n,1≤j≤n}
定义:若可以在平面中画出一个图而边没有任何交叉(其中边的交叉是表示边的直线或弧线在它们的公共端点以外的地方相交),则这个图是平面图。这种画法称为这个图的平面表示。


定理(欧拉公式):设G是带e条边和v个顶点的连通平面简单图。设r是G的平面图表示中的面数,则r=e-v+2
举例:假定连通平面简单图有20个顶点,每个顶点的度都为3。这个平面图的平面表示把平面分割成多少个面?
由题意可得 v=20,因为3×v=2×e(一条边有两个端点,而端点数对应所有顶点的度),所以e=30,r = e - v + 2 = 12
推论:若G是e条边和v个顶点的连通平面简单图,其中v≥3,则e≤3v-6
首先可以确定的是一个面的度数是大于或等于3的(一个三角形有3个顶点),所以有
推论:若G是连通平面简单图,则G中有度数不超过5的顶点。
假设G中的度数全部大于5,所以有2e≥6v,而e≤3v-6,所以存在矛盾,G中有度数不超过5的顶点。
推论:若连通平面简单图有e条边和v个顶点,v≥3并且没有长度为3的回路,则e≤2v-4。
若一个图是平面图,则通过删除一条边{u,v}并且添加一个新顶点w和两条边{u,w}与{w,v}获得的任何图也是平面图,这样的操作称为初等细分。若可以从相同的图通过一系列初等细分来获得图

定理:一个图是非平面图当且仅当它包含一个同胚于
![]() | ![]() |
定义:简单图的着色是对该图的每个顶点都指定一种颜色,使得没有两个相邻的顶点颜色相同。
定义:图的着色数是着色这个图所需要的最少颜色数。图G的着色数记作
定理(四色定理):平面图的着色数不超过4。
举例:
举例:完全二分图
举例:图
举例:安排期末考试,使得没有学生同时要考两门,假设一共有7门课,用1-7来表示,不同的颜色表示不同时间段。

定义:树是没有简单回路的连通无向图
因为树没有简单回路,所以树不含多重边或环,因此任何树都必然是简单图。
定理:一个无向图是树当且仅当在它的每对顶点之间存在唯一简单通路。
定义:有根树是指定一个顶点作为根并且每条边的方向都离开根的树。
定义:若有根树的每个内点都有不超过m个孩子,则称它为m叉树。若该树的每个内点都恰好有m个孩子,则称它为满m叉树。把m=2的m叉树称为二叉树。
定理:带有n个顶点的树含有n-1条边。
定理:带有i个内点的满m叉树含有n=mi+1个顶点。
定理:一个满m叉树若有
(1)n个顶点,则有i=(n-1)/m个内点和l=[(m-1)n+1]/m个树叶;
(2)i个内点,则有n=mi+1个顶点和l=(m-1)i+1个树叶;
(3)l个树叶,则有n=(ml-1)/(m-1)个顶点和i=(l-1)/(m-1)个内点。
若一棵高度为h的m叉树的所有树叶都在h层或h-1层,则这棵树是平衡的。
定理:在高度为h的m叉树中至多有
推论:若一棵高度为h的m叉树带有l个树叶,则
二叉搜索树是一种二叉树,其中任何顶点的每个孩子都指定为右子或左子,没有顶点有超过一个的右子或左子,而且每个顶点都用一个关键字来标记,这个关键字是各元素中的一个。另外,这样指定顶点的关键字,使得顶点的关键字不仅大千它的左子树里的所有顶点的关键字,而且小千它的右子树里的所有顶点的关键字。
若二叉搜索树是平衡的,则确定一个元素的位置或者添加一个元素所需要的比较次数不超过
二叉搜索树可以用来基于一系列比较来找出元素的位置,其中每次比较都说明是否已经找到了元素的位置,或者是否应当向右或向左进入子树。其中每个内点都对应着一次决策,这些顶点的子树都对应着该决策的每种可能结果,这样的有根树称为决策树。问题的可能解对应着这个有根树中通向树叶的通路。
n个元素的排序有n!种。
定理:基于二元比较的排序算法至少需要
引理:基于二元比较的排序算法排序n个元素所用的比较次数是
定理:基于二元比较的排序算法排序n个元素所用的平均比较次数是
哈夫曼编码不过多赘述。
博弈树的树叶表示游戏的终局。给每个树叶指定一个值,表示游戏在这个树叶所代表的局面终止时第一个选手的得分。对于非胜即负的游戏,用1来标记圆圈所表示的终结顶点以表示第一个选手获胜,用-1来标记方框所表示的终结顶点以表示第二个选手获胜。对于允许平局的游戏,用0来标记平局所对应的终结顶点。注意,对于非胜即负的游戏,为终结顶点指定值,这个值越高,第一个选手的结局就越好。
定义:博弈树中顶点的值递归地定义为: (1)一个树叶的值是当游戏在这个树叶所表示的局面里终止时第一个选手的得分。 (2)偶数层内点的值是这个内点的孩子的最大值,奇数层内点的值是这个内点的孩子的最小值。
使第一个选手移动到具有最大值的孩子所表示的局面并且第二个选手移动到具有最小值的孩子所表示的局面的策略称为最小最大策略。
定理:博弈树顶点的值说明,如果两个选手都遵循最小最大策略并且从博弈树的某一个顶点所表示的局面开始进行游戏,则这个顶点的值表明第一个选手的得分。
常用的遍历算法有前序遍历、中序遍历和后序遍历
定义(前序遍历):设T是带根r的有序根树。若T只包含r,则r是T的前序遍历。否则,假定
定义(中序遍历):设T是带根r的有序根树。若T只包含r,则r是T的中序遍历。否则,假定
定义(后序遍历):设T是带根r的有序根树、若T只包含r,则r是T的后序遍历。否则,假定
前序遍历
procedure preorder(T: 有序根树)
r := T的根
打印r
for 从左到右的r的每个孩子c
T(c) := 以c为根的子树
preorder(T(c))
中序遍历
procedure inorder(T:有序根树) r := T的根 if r 是树叶 then 打印r else i := 从左到右的r的第一个孩子 T(l) := 以l为根的子树 inorder(T(l)) 打印r for 除l外从左到右的r的每个孩子c T(c) := 以c为根的子树 inorder(T(c))
后序遍历
procedure postorder(T:有序根树)
r := T的根
for 从左到右的r的每个孩子c
T(c) := 以c为根的子树
postorder(T(c))
打印r
前序遍历对于内部顶点必须在叶子顶点前访问的应用来说是最佳选择,此外,前序遍历还用于复制二叉搜索树。后序遍历对于叶子顶点需要在内部顶点之前访问的应用来说是最佳选择。后序遍历在访问内部顶点之前访问叶子顶点,所以,它对于删除树是最佳选择,因为子树根顶点下面的顶点可以在子树的根顶点之前删除。拓扑排序是一种使用后序遍历实现的高效算法。
可以用有序树来表示复杂的表达式,比如复合命题、集合的组合,以及算术表达式。例 如,考虑由运算+(加)、-(减)、* (乘)、/(除)、↑(幂)所组成的算术表达式的表示。
举例:((x+y)↑2) + ((x-4) / 3)的有序根树是什么

上面这张图显示的是中缀形式,当以前序遍历表达式的有根树时,就获得它的前缀形式,写成前缀形式的表达式称为波兰记法。通过以后序遍历表达式的二叉树,就可以获得它的后缀形式,写成后缀形式的表达式称为逆波兰记法。
前缀表达式和后缀表达式都是无二义性的。
定义:设G是简单图。G的生成树是包含G的每个顶点的G的子图。
定理:简单图是连通的当且仅当它有生成树。
深度优先搜索的操作:任意选择图中一个顶点作为根。通过依次添加边来形成从这个顶点开始的通路,其中每条新边都与通路上的最后一个顶点以及还不在通路上的一个顶点相关联。继续尽可能地添加边到这条通路。若这条通路经过图的所有顶点,则由这条通路组成的树就是生成树。不过,若这条通路没有经过图中的所有顶点,则必须添加其他的顶点和边。退到通路中的倒数第二个顶点,若有可能,则形成从这个顶点开始的经过还没有访问过的顶点的通路。若不能这样做,则后退到通路中的另一个顶点,即在通路里后退两个顶点,然后再试。
重复这个过程,从所访问过的最后一个顶点开始,在通路上一次后退一个顶点,只要有可能就形成新的通路,直到不能添加更多的边为止。因为这个图有有穷的边数并且是连通的,所以这个过程以产生生成树而告终。在这个算法的一个阶段上通路末端的顶点将是有根树中的树叶,而在其上开始构造一条通路的顶点将是内点。
这个过程的本质是递归,若图中的顶点是排序的,则当总是选择在该顺序里可用的第一个顶点时,在这个过程的每个阶段上对边的选择就全都是确定的。不过,将不总是明显地对图的顶点排序。深度优先搜索也被称为回溯,因为这个算法返回以前访问过的顶点以便添加边。
深度优先搜索
procedure DFS(G: 带顶点
,..., 的连通图) T := 只包含顶点 的树 visit( )
procedure visit(v: G的顶点) for 与v相邻并且还不在T中的每个顶点w 加入顶点w和边{v,w}到T visit(w)
计算复杂度为
从图的顶点中任意地选择一个根,然后添加与这个顶点相关联的所有边。在这个阶段所添加的新顶点成为生成树在第1层上的顶点,将新顶点任意排序。下一步,按顺序访问第1层上的每个顶点,只要不产生简单回路,就将与这个顶点相关联的每条边添加到树中。任意排序第一层的每个顶点的孩子,这样就产生了树在第2层上的顶点。遵循相同的过程,直到巳经添加了树中的所有顶点。因为在图中的边数是有限的,所以这个过程会终止。在产生了包含图中每一个顶点的树之后,生成树也就产生了。
宽度优先搜索
procedure BFS(G:带顶点
,..., 的连通图) T := 只包含顶点 的树 L := 空表 把 放入尚未处理顶点的表L中 while L 非空 删除L中第一个顶点v for v 的每个邻居 w if w 既不在L中也不在T中 then 加入w到表L的末尾 加人w和边{v,w}到T
举了图着色和n皇后的例子,不过多赘述
可以轻而易举地修改深度优先搜索和宽度优先搜索,使得以有向图作为输入时它们也能运行。但是,输出不一定是生成树,而可能是森林。在这两个算法中,只有当一条边从正在访问的顶点出发并且到一个尚未加入的顶点时才加入这条边。如果在其中任何一个算法的某个阶段找不到从已经加入的顶点到尚未加入的顶点的边,则算法加入的下一个顶点成为生成森林中一个新树的根。
举例:给定左图作为输入,深度优先搜索的输出是右图

从顶点a开始深度优先搜索并且加入顶点b、e和g以及相对应的边,直到无路可走。回溯到c,但是仍然无路可走,于是回溯到b,这里加入顶点j和e以及对应的边,回溯最终又回到a。然后在d开始一个新的树并且加人顶点h、l、k和j以及对应的边。回溯到k,然后到l,然后到h并且回到d。最后,在i开始一个新的树,完成深度优先搜索。
定义:连通加权图里的最小生成树是具有边的权之和最小的生成树。
普林算法
procedure Prim(G:带n个顶点的连通加权无向图)
T := 权最小的边 for i := 1 to n-2 e := 与T里顶点关联且若添加到T里则不形成简单回路的权最小的边 T := 添加e之后的T return T {T是G的最小生成树}
判断是否形成简单回路可以观察边数是否等于顶点-1(不一定正确)。
克鲁斯卡尔算法
procedure Kruskal(G:带n个顶点的加权连通无向图) T := 空图 for i := 1 to n-1 e := G中权最小的任一边且当添加到T里时不形成简单回路边 T := T 添加 e return T {T是G的最小生成树}
在普林算法里,选择与已在树中的一个顶点相关联且不形成回路的权最小的边;相对地,在克鲁斯卡尔算法里,选择不一定与已在树中的一个顶点相关联且不形成回路的权最小的边。
设B={0,1},则
到B的函数称为n元布尔函数。
问:给定一个布尔函数的值,怎样才能找到表示这个布尔函数的布尔表达式?
答:任何一个布尔函数都可由变元及其补的布尔积的布尔和表示。
有没有一个更小的运算符集合可以用来表示所有的布尔函数?
答:所有的布尔函数都可以仅用一个运算符来表示。
定义:布尔变元或其补称为字面值。布尔变元
举例:求一个极小项使得当
极小项
举例:求函数
每个布尔函数都可以表示为极小项的布尔和。每个极小项都是布尔变元或其补的布尔积。这说明每个布尔函数都可以用布尔运算·、+和⁻来表示,因为每个布尔函数都可以由这些布尔运算表示,所以我们称集合{·,+,⁻}是函数完备的。
因为
因为
注意{+,·}不是函数完备的。
定义运算符|或NAND如下:1|1=0且1|0=0|1=0|0=1,定义运算符↓或NOR如下:1↓1=1↓0=0↓1=0且0↓0=1。集合{|}和集合{↓}都是完备的,只需证明两个运算·和⁻可以由|或↓表示即可
构造三种组合电路:反相器、或门和与门

举例:某个组织的一切事务都由一个三人委员会决定,每个委员对提出的建议可以投赞成票或反对票,一个建议如果得到了至少两张赞成票就获通过。设计一个电路,判断建议是否获得通过。
假设输入为x、y和z,布尔函数表示为xy+xz+yz,电路如下图所示

举例:假设真值表如下表所示
| x | y | z | F(x,y,z) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 |
观察F(x,y,z)=1时对应的x、y和z的值,如果是0就取反,最后可以得到积之和表达式为
后面还提到半加法器和全加法器的电路,不再过多介绍。
积之和展开式可能存在多余的项,如下式就可以合并
在该布尔函数的所有积之和表达式中,包含最少的布尔积而且包含最少的字面值。寻求这种积之和称为布尔函数的最小化。
一种可视化的用于寻找最小化布尔函数的方法。
举例:找出下式的卡洛图:(a)

在化简时将相邻的进行化简,如

对于三个变元,可以采用以下方法

(1)将由n个变元构成的每一个极小项表示成一个长度为n的比特串,如果
(2)根据串中1的个数将串分组
(3)确定所有这样n-1个变元的积,它们可以通过取展开式中极小项的布尔和得到。将能够
合并的极小项表示成比特串,且这些串只在一个位置不相同。将这些n-1个变元的积用如下的串表示:如果
(4)确定所有这样n-2个变元的积,它们可以取为在前一个步骤形成的n-1个变元的积的布尔和。将能够合并的n-1个变元的积,表示成如下的串:在同一位置有一个短划线,且只在一个位置不相同。
(5)只要可能,继续将布尔积合并成更少变元的积。
(6)找到所有这样的布尔积:它们虽然出现,但还没有被用来形成少一个字面值的布尔积。
(7)找到这些布尔积的最小集合,使得这些积之和表示此布尔函数。这可以用如下方法来完 成:构造一个表,列出哪些积覆盖了哪些极小项,每一个极小项必定被至少一个积覆盖。使用此表的第一步是找到所有的本原素隐含。每个本原素隐含必须被包含,因为它是覆盖某个极小项的唯一素隐含。如果找到了本原素隐含,就可以通过除去由此素隐含覆盖的极小项的行化简此表。第二步,去掉所有满足如下条件的素隐含,此素隐含覆盖一个极小项集合,此极小项集合被另一个素隐含覆盖。第三步,从表中去掉满足如下条件的极小项所在的行,覆盖此极小项的某些素隐含也覆盖另一个极小项。首先找到必须被包含的本原素隐含,然后去掉冗余的素隐含,最后找到可以被忽略的极小项,迭代此过程直到此表不再改变为止。这里使用回溯过程寻找最优解,为覆盖所有的字面值积逐步添加素隐含以寻找可能的解,在每一步都与已经找到的最优解进行比较。
感觉不太好理解
定义:词汇表(或字母表)V是由称为符号的元素构成的一个有限的非空集合。V上的一个词(或句子)是由V中元素组成的有限长度的字符串。空串(或零串)是不包含任何符号的字符串,记为λ,V上所有词的集合记为
注意,空串λ是不包含任何符号的串,它不同于空集⌀。因此{λ}是仅包含一个字符串的集合,此字符串为空串。
V是一个由符号组成的集合,语言中的成分就是由这些符号导出的。词汇表中的某些元素不能由其他符号替换,这些元素称为终结符;词汇表中的其他元素可以用其他符号替换,它们称为非终结符。
定义:一个短语结构文法G=(V,T,S,P)由下列四部分组成:词汇表V,由V的所有终结符组成的V的子集T,V的起始符S,以及产生式集合P。集合V—T记为N,N中的元素称为非终结符。P中的每个产生式的左边必须至少包含一个非终结符。
定义:设G=(V,T,S,P)是一个短语结构文法,
定义:设G=(V,T,S,P)是短语结构文法,由G生成的语言(或G的语言)是起始符S能够派生的所有终结符串构成的集合,记为L(G)。即
一开始介绍了一些文法,范式的内容
定义:有限状态机M=(S,I,O,f,g,
举例:根据状态表构造有限状态机

在左表中,f代表输入0或1时的下一个状态,g代表输入0或1时的输出,刚开始状态
输出与状态之间的转移相对应,这种类型的机器称为米兰机;
输出仅仅由状态确定,这种类型的有限状态机称为摩尔机。
定义:设V是一个词汇表,A、B是
举例:设A={0,11},B={1,10,110}。求AB和BA
集合AB包括所有A中串和B中串的连接,故AB = {01,010,0110,111,1110,11110}
集合BA包括所有B中串和A中串的连接,故BA = {10,111,100,1011,1100,11011}
定义:设A是
定义:有限状态自动机M=(S,I,f,
到目前为止所讨论的有限状态自动机都是确定性的,因为对每对状态和输入值,转移函数只给出唯一的下一个状态。还有一种重要的有限状态自动机,它对每对输入值和状态,有多个可能的下一个状态,这样的机器称为非确定性的。非确定性的有限状态自动机在判断哪些语言可以由有限状态自动机识别中非常重要。
定义:非确定性的有限状态自动机M=(S,I,f,
非确定性的有限状态自动机也可用状态表和状态图来表示。在状态表中,对每对状态和输入值,列出所有可能的F一个状态。在状态图中,从一个状态到每个可能的下一个状态,都画一条边,这条边的标号是导致这个转移的一个或多个输入。
定理:如果语言L可以由非确定性的有限状态自动机
一个集合能够被一个有限状态自动机识别当且仅当这个集合是以任意顺序通过对空集、空串和单字符串的连接、并或克莱因闭包构造出来。以这种方法构造出来的集合称为正则集合。
定义:集合I上的正则表达式的递归定义为:
符号⌀是一个正则表达式;
符号λ是一个正则表达式;
若x∈I时,则符号x是一个正则表达式;
当A、B是正则表达式时,符号(AB)、(
定理(克莱因定理):一个集合是正则的,当且仅当它可由一个有限状态自动机识别。
定义:图灵机T=(S,I,f,
图灵机主要由一个控制器和一个纸带组成,控制器在任何时候都处于有限多个不同状态中的某 个状态,纸带被分成许多方格,且两端都是无限的。当图灵机的控制器沿着纸带来回移动时,它能够在带上读和写,并根据所读的纸带符号改变状态。图灵机比有限状态自动机更强大,因为它有存储能力,而有限状态自动机却没有。
为了用机器的观点来解释这个定义,考察控制器和纸带,如下图所示,纸带被分成小方格,且两端都是无限的,在任何时刻其上都只有有限多个非空白符。图灵机运行的每一步动作依赖于部分函数对当前状态和纸带符号的值。

在每一步,控制器读当前纸带符号x,如果控制器处于状态s,且部分函数f在(s,x)处由f(s,x)=(s',x',d)定义,则控制器:
(1)进入状态s';
(2)在当前方格中擦掉x,并写上符号x';
(3)如果d=R,向右移动一个方格;如果d=L,向左移动一个方格。
我们将这一步写成五元组(s,x,s',x',d)。如果部分函数f在(s,x)处没有定义,则图灵机T 就停机。定义一个图灵机的常用方法是指明形如(s,x,s',x',d)的五元组构成的一个集合。
定义:设V是字母表I的一个子集。图灵机T=(S,I,f,
示例:求一个图灵机,使之能识别第二位是1的比特串构成的集合,即正则集合
我们想要如下的图灵机,它从最左边的非空白带方格开始运行,然后向右移动,同时判断第二个符号是否为1。若第二个符号是1,则机器应该进入终结状态;如果第二个不是1,则机器不能停机,或者在一个非终结状态下停机。
为了构造这样的图灵机,应该包括五元组(
由上述7个五元组组成的图灵机T在终结状态
可以将图灵机看作能求部分函数的值的计算机。为了理解这一点,假设给定输入字符串x时图灵机T能够停机,且停机时,字符串y在它的纸带上。因此可以定义T(x)=y。T的定义域是使T能停机的字符串构成的集合。对于输入x,若T不停机,则T(x)没有定义。将图灵机看成计算字符串的函数值的机器是有用的,但怎么用图灵机来计算定义在整数、整数对或整数三元组等上的函数呢?
为了将图灵机看作计算k元非负整数集合到非负整数集合的函数(这样的函数称为数论函数)的计算机,需要找到在纸带上表示整数的k元组的方法。为此,我们使用整数的一元表示,即将非负整数n表示成有n+1个1的字符串。例如,0表示成字符串1、5表示成字符串111111。为了表示k元组(
举例:构造一个图灵机,它将两个非负整数相加。
需要构造图灵机来计算函数f(
不幸的是,即使是相对简单的函数,构造图灵机来计算它也是极为费力的。
丘奇—图灵论题:对于任何可用有效算法来求解的问题,都存在解该问题的图灵机。
注意不是定理
定义:判定问题是指判断某个特定类型的命题是否为真,判定问题也被称为“是或不是”问题。
当有一个有效的算法能够判断判定问题的某个解是否正确时,我们说这个问题是可解的或者说是可判定的。
如果不存在一个算法来解决某个问题,那么就称该问题是不可解的或者说不可判定的。为了证明某个问题是可解的,只需要构造一个算法来判定某类特定的描述是否正确。另一方面,为了证明某个问题是不可解的,需要证明不存在这样一个判定算法就可以了(事实上,我们试图找到这样的算法,但失败了,不能证明该问题是不可解的)。
如果一个函数可以被图灵机计算,那么就称其是可计算的,否则是不可计算的。
定义:如果一个判定问题能由确定性的图灵机在多项式时间内求解,则该问题属于Р类问题,即多项式时间问题。也就说,如果一个确定性的图灵机T和一个多项式P,对于该问题的任何长度为n的字符串,T都能在P(n)步内停机,我们说该问题属于P类。如果一个判定问题能由非确定性的图灵机在多项式时间内求解,则该问题属于NP类问题,即非确定性的多项式时间问题。也就是说,对于任一判定问题,如果存在一个非确定性的图灵机T和一个多项式P,对于该问题的任何长度为n的实例,T都能在P(n)步内停机,则称该问题是NP类问题。
P类问题称为易处理的问题,而不属于P类问题称为不易处理的问题。